#include <iostream>
#include <cstdbool>
using namespace std;


namespace YX
{
    // 结点
    template<class T>
    struct ListNode
    {
        ListNode<T>* _prev;
        ListNode<T>* _next;
        T _data;
        
        ListNode(const T& data)
            :_prev(nullptr)
            ,_next(nullptr)
            ,_data(data)
        {
            _prev=this;
            _next=this;
        }
    };

    template<class T,class REF,class PTR>
    struct _list_iterator
    {
        ListNode<T>* _iterator;

        _list_iterator(ListNode<T>*& it)
            :_iterator(it)
        {
    
        }
        
        bool operator==(const _list_iterator<T,REF,PTR>& list_it)
        {
            return this->_iterator==list_it._iterator;
        }

        bool operator!=(const _list_iterator<T,REF,PTR>& list_it)
        {
            return this->_iterator!=list_it._iterator;
        }

        REF operator*()
        {
            return _iterator->_data;
        }

        _list_iterator<T,REF,PTR>& operator++()
        {
            _iterator=_iterator->_next;

            return *this;
        }

        PTR operator->()
        {
            return &(operator*());
        }

    };


    template<class T>
    class List 
    {
        private:
            typedef ListNode<T> Node;

            Node* _head;

        public:
                
            typedef _list_iterator<T,T&,T*> Iterator;
            typedef _list_iterator<T,const T&,const T*> const_Iterator;

            List()
                :_head(nullptr)
            {
                _head=new Node(T());
            }

            void push_back(const T& val)
            {
                Node* tail=_head->_prev;

                Node* newNode=new Node(val);

                tail->_next=newNode;
                newNode->_prev=tail;

                _head->_prev=newNode;
                newNode->_next=_head;
            }
            
            Iterator begin()
            {
                return Iterator(_head->_next);
            }

            Iterator end()
            {
                return Iterator(_head);
            }
            
            const_Iterator begin() const 
            {
                return Iterator(_head->_next);
            }

            const_Iterator end() const 
            {
                return Iterator(_head);
            }

            Iterator insert(Iterator pos,const T& val)
            {
                Node* newNode=new Node(val);


                Node* curr=pos._iterator;

                curr->_prev->_next=newNode;
                newNode->_prev=curr->_prev;

                curr->_prev=newNode;
                newNode->_next=curr;
                

                return Iterator(newNode);
            }

            Iterator erase(Iterator pos)
            {
                Node* del=pos._iterator;

                Node* prev=del->_prev;
                Node* next=del->_next;

                prev->_next=next;
                next->_prev=prev;

                delete del;

                return del;
            }
            


    };

    void TestList1()
    {
        List<int> l;

        l.push_back(1);
        l.push_back(2);
        l.push_back(3);
        l.push_back(4);
        l.push_back(5);
        l.push_back(6);
        l.push_back(7);

        List<int>::Iterator it=l.begin();

        while(it!=l.end())
        {
            cout<<*it<<" ";
            ++it;
        }
        cout<<endl;
        
        l.insert(l.begin(),0);
        
        it=l.begin();

        while(it!=l.end())
        {
            cout<<*it<<" ";
            ++it;
        }
        cout<<endl;


    }

};
